Context-free path querying with all-path semantics using matrices with sets of intermediate vertices.
Annotation
The study considers the problem of context-free path querying with all-path query semantics. This problem consists in finding all paths of the graph, the labels on the edges of which form words from the language generated by the input context-free grammar. There are two approaches to evaluate context-free path queries using linear algebra operations: matrix multiplication-based and the Kronecker product-based. But until now, there is no algorithm using the matrix multiplication capable of handling context-free path queries with the most complex all-path query semantics, in which the all paths that match the query must be provided. The paper proposes the algorithm for context-free path query evaluation using the matrix multiplication, which is capable of processing queries with the all-path query semantics. In the adjacency matrix of the input graph for each pair of vertices, we store additional information about the paths found between these vertices in the form of a set of possible intermediate vertices. At the first stage, a set of matrices is constructed that store such information about all paths that satisfy the input query. At the second stage, all queried paths are restored from the constructed set of matrices. The proposed algorithm was implemented in C++ and a comparison was made with other most efficient algorithms for evaluating context-free path queries, namely with the matrix-based algorithm that allows us to find only one such path, and with the Kronecker product-based algorithm that allows us to find all such paths in the graph. The results of the experimental study showed that the proposed algorithm is significantly more efficient in restoring the queried paths, but in some cases it consumes a significantly larger amount of memory than the algorithm based on the Kronecker product. The described algorithm can be applied in static code analysis, bioinformatics, network analysis, as well as in graph databases, when it is required to find all possible dependencies in the data presented in the form of a labeled graph.
Keywords
Постоянный URL
Articles in current issue
- On the feasibility of the monostatic scheme for constructing the land-based telescope at supervision of space objects
- DREM procedure application for piecewise constant parameters identification
- Features of the morphology of micro- and nanoporous copper and silver films synthesized by substitution reaction for photocatalytic application.
- Nature-inspired metaheuristic scheduling algorithms in cloud: a systematic review
- Evaluation of the applicability of asynchronous programming methods to the data consistency problem in a microservices environment
- A factor model for detection and recognition of human face contours and elements
- A study of the stability of information and telecommunication networks under conditions of stochastic percolation of nodes
- Decision support system for the proton therapy implementation
- Determination of dangerous driving behavior based on the use of information from wearable electronic devices
- An automata-based programming engine
- Bayesian losses for homoscedastic aleatoric uncertainty modeling in pollen image detection
- The speech synthesis detection algorithm based on cepstral coefficients and convolutional neural network
- Risk assessment methodology for information systems, based on the user behavior and IT-security incidents analysis
- Identification of user accounts by image comparison: the pHash-based approach
- A study of human motion in computer vision systems based on a skeletal model
- Solution of super- and hypersonic gas dynamic problems with a model of high-temperature air
- Modeling security violation processes in machine learning systems
- Mathematical modeling of an optimal oncotherapy for malignant tumors.
- A numerical study of the expansion of a gas-particles mixture with axial symmetry.
- The study of the birefrigence modulator based on lithium niobate